#include <string>
#include <iostream>
#include <vector>
#include <fstream>
#include "util.h"
#include "jqsort.h"
#include "integerarray.h"
#include "corpus.h"

#ifndef _SUFFIXINDEX_H_
#define _SUFFIXINDEX_H_

// This lets you search a character array for subarrays.
// It does so by sorting the suffixes so they can be binary-searched.

struct SuffixSorter {
  // call these three functions
  void Init(Corpus *corpus, IntegerArray *positions);
  void Sort();
  void VerifySort();
  void Store(string fn);

  // for internal use
  void MakeRollingHash();
  uint64 PointRollingHash(uint64 n);
  uint64 ComputeRollingHash(uint64 begin, uint64 end); 
  int64 CompareSuffixes(uint64 p1, uint64 p2);

  struct PositionCompare {
    PositionCompare(SuffixSorter * ss) { ss_ = ss; }
    SuffixSorter *ss_;
    bool operator()(uint64 c1, uint64 c2) const {
      return (ss_->CompareSuffixes(c1, c2) < 0); } };
  
  Corpus *corpus_;
  IntegerArray *positions_;

  // stuff related to rolling hash.  
  // The rolling hash is used at index time to avoid quadratic complexity. 
  uint64 * rolling_hash_;
  // the rolling hash is only computed every this many steps, to save memory.
  int rolling_hash_sparsity_;
  uint64 k_;
  // for fast exponentiation base k_; maps n -> k_ ^ (2 ^ n)
  uint64 * k_pow_2_pow_n_;
};

struct SuffixIndex {
  void Init(Corpus *corpus, Memblock index);
  // void VerifySort();
  uint64 Get(uint64 i) { return index_.Get(i); }

  // Input string is represented by a pointer and length
  // Output is a range in the index.
  pair<uint64, int64> Search(uint32 *target_begin, uint64 target_length);
  
  // internals

  struct Searcher{
  Searcher(SuffixIndex *si, uint32 *target_begin, 
	   uint64 target_length, bool second_wins) 
  :target_begin_(target_begin),
      target_length_(target_length), 
      si_(si), 
      second_wins_(second_wins) {}
    bool operator() (int64 position) {
      uint64 p = si_->index_.Get(position); 
      return si_->Compare(p, si_->corpus_->size() - p,
			  target_begin_, target_length_, second_wins_) >= 0; }
    uint32 * target_begin_;
    uint64 target_length_;
    SuffixIndex *si_;
    bool second_wins_;
  };
  
  int64 Compare(uint64 corpus_position, uint64 l1, 
		 uint32 *v2, uint64 l2, 
		 bool second_wins = false);

   // DATA SECTION
  Corpus *corpus_;
  
  // an array of length data_size_ containing positions sorted by the
  // lexicographic order of the suffixes starting at those positions. 
  IntegerArray index_;
};

void suffixindex_main(string filename);

#endif
